package com.itheima.leetcode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;
import java.util.stream.Collectors;

/**
 * 跳表
 */
public class SkipListLeetcode1206 {

    public static void main(String[] args) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < 1000; i++) {
            int level = randomLevel(5);
            map.compute(level, (k, v) -> v == null ? 1 : v + 1);
        }
        System.out.println(map.entrySet().stream().collect(
                Collectors.toMap(
                        Map.Entry::getKey,
                        e -> String.format("%d%%", e.getValue() * 100 / 1000)
                )
        ));

        Skiplist list = new Skiplist();

        list.add(1);
        list.add(2);
        list.add(3);
        list.search(0);   // 返回 false
        list.add(4);
        list.search(1);   // 返回 true
        list.erase(0);    // 返回 false，0 不在跳表中
        list.erase(1);    // 返回 true
        list.search(1);   // 返回 false，1 已被擦除

        System.out.println(Arrays.toString(list.find(30)));
    }

    /*
        设计一个方法，方法会随机返回 1 ~ max 的数字
        从 1 开始，数字的几率逐渐减半，例如 max = 4，让大概
            - 50% 的几率返回 1
            - 25% 的几率返回 2
            - 12.5% 的几率返回 3
            - 12.5% 的几率返回 4
     */
    static Random r = new Random();

    static int randomLevel(int max) {
//        return random.nextBoolean() ? 1 : random.nextBoolean() ? 2 : random.nextBoolean() ? 3 : 4;
        int x = 1;
        while (max > x) {
            if (r.nextBoolean()) {
                return x;
            }
            x++;
        }
        return x;
    }

    static class Skiplist {
        private static final int MAX = 10; // redis 32 java 62
        private final Node head = new Node(-1);

        static class Node {
            int val; // 值
            Node[] next = new Node[MAX]; // next 数组

            public Node(int val) {
                this.val = val;
            }

            @Override
            public String toString() {
                return "Node{" +
                        "val=" + val +
                        ", next=" + Arrays.toString(next) +
                        '}';
            }
        }

        public Node[] find(int val) {
            Node[] path = new Node[MAX];
            Node curr = this.head;
            for (int level = MAX - 1; level >= 0; level--) { // 从上向下找
                while (null != curr.next[level] && val > curr.next[level].val) { // 向右
                    curr = curr.next[level];
                }
                path[level] = curr;
            }
            System.out.println(curr);
            return path;
        }

        public boolean search(int val) {
            Node[] path = find(val);
            Node node = path[0].next[0];
            return null != node && val == node.val;
        }

        public void add(int val) {
            // 1. 确定添加位置（把 val 当作目标查询，经历的路径就可以确定添加位置）
            Node[] path = find(val);
            // 2. 创建新节点随机高度
            Node node = new Node(val);
            int level = randomLevel(MAX);
            // 3. 修改路径节点 next 指针，以及新节点 next 指针
            for (int i = 0; i < level; i++) {
                node.next[i] = path[i].next[i];
                path[i].next[i] = node;
            }
        }

        public boolean erase(int val) {
            Node[] path = find(val);
            Node node = path[0].next[0];
            if (null == node || val != node.val) {
                return false;
            }
            for (int i = 0; i < MAX; i++) {
                if (node != path[i].next[i]) {
                    break;
                }
                path[i].next[i] = node.next[i];
            }
            return true;
        }
    }
}
